/**
 * 面试题56-1：数组中只出现一次的两个数字
 */
public class Offer_56_I {
    /**
     * 分组异或
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public int[] singleNumbers(int[] nums) {
        // 计算所有数字的异或结果，即是 x 和 y 的异或结果
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        // 循环左移，找到结果数字中第一个为 1 的位的位置（从右起）
        int div = 1;
        while ((div & res) == 0) {
            div <<= 1;
        }
        // 以第 div 位是不是 1 为标准，将数组分为两部分
        // 这样问题就转化为：在一个数组中，除了一个数字以外，其他数字都出现了两次，找出该数字
        int x = 0, y = 0;
        for (int num : nums) {
            if ((div & num) != 0) {
                // 第 div 位是 1
                x ^= num;
            } else {
                // 第 div 位不是 1
                y ^= num;
            }
        }
        return new int[] { x, y };
    }
}
